COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	~[Cλ30P70JCFA section 7.
C00007 00003	COMPARING.
C00011 ENDMK
C⊗;
~[C;λ30;P70;JCFA section 7.
~JCFD IMAGE COMPARING.

[7.0	Introduction to Image Comparing.]
~JUFA
	The compare step of  CRE,  CMPARE, connects the  polygons and
arcs  of the current  image with  corresponding polygons and  arcs of
the  previous image.    CMPARE  solves  the  problem  of  correlating
features  between  two  similar  images  and  is  composed  four  sub
sections: 

	1. make shape nodes for polygons.
	2. compare and connect polygons one to one.
	3. compare and connect polygons two to one.
	4. compare and connect vertices of connected polygons.

	First,  the shape  nodes of all the polygons of  an image are
computed. The  shape node contains the center  of mass and the lamina
inertia tensor of a polygon.  The lamina inertia tensor of  a polygon
with  N sides  is  computed  by summation  over  N  trapezoids.   The
trapezoid   corresponding  to   each  side  is   formed  by  dropping
perpendiculars  "up"  to the  top  of  the  image  frame;  each  such
trapezoid  consists of  a rectangle  an a  right triangle;  since the
sides of polygons  are directed  vectors the areas  of the  triangles
and rectangles can be  arranged to take positive and  negative values
such  that  a summation  will  describe the  interior  region  of the
polygon  as positive.  The  equations  necessary  for  computing  the
lamina inertia  tensor of a polygon  are collected in a  table in the
postscripts  to  this paper  and  were derived  by  using Goldstein's
Classical Mechanics [1] as a  reference.  The meaning of  the inertia
tensor  is that it  characterizes each  polygon by  a rectangle  of a
certain length and width at a particular location and oriention;  and
of  further  importance  such  inertia  tensors  can  be  "added"  to
characterize two  or more polygons by a single  rectangle.  It is the
lamina inertia tensor rectangles that are actually compared by CRE.

	Second, all the shapes  of the polygons  of one level of  the
first image are  compared with all the shapes of  the polygons of the
corresponding level  of the second image for nearly exact match.  The
potentially (M*N/2) compares is  avoided by sorting on the  center of
mass locations.   In CRE,  which is intended  for comparing sequences
of pictures of natural scenes; match  for center of mass location  is
tested first  and  most strictly,   followed  by  match for  inertia.
Pointers  between  matching  polygons are  placed  in  the time  link
positions of the polygon nodes and the polygons are considered  to be
mated in time.
COMPARING.

	Third,  all  the unmated polygons  of a level  are considered
two  at a time and  a fusion shape node  for each pair is  made.  The
potentially (N*N/2-N) fusion  shapes are avoided  because there is  a
maximum possible  unmated inertia  in the other  image; lo,  if there
are  no unmated polygons in one image  then the extra polygons of the
first image  can be  ignored. In the  event where  there are  unmated
polygons  in  corresponding levels  of  the  two  images, the  fusion
shapes of one  are compared  with the  polygon shapes  of the  other.
The  fusion  (fission)  compare  solves  the  rather  nasty  problem,
illustrated in  figures 9A and 9B of  linking two contour polygons of
one image with a single contour polygon in the next image.

	Fourth, the vertices of  polygons mated in time are  compared
and mated.  To start a  vertex compare,  the vertices of  one polygon
are  translated,   rotated and dilated  to get  that polygon's lamina
inertia tensor  coincidant with  its mate  (or mates).  Conceptually,
each vertex of one polygon  is compared with each vertex of the other
polygon(s)  and  the  mutually  closest  vertices  (closer  than   an
epsilon) are  considered to  be mated.  Actually the potential  (N*M)
compares  is avoided by  a window  splitting scheme similiar  to that
used in hidden line elimination algorithms (like Warnock's).

	The results  of vertex compare  and mate  are illustrated  in
figures 9A and 9D; the compare  execution takes less than a second on
images  such as the  pump,  blocks,  and dolls that  have appeared in
this  paper. The  applications  of  this compare  might  include  the
aiming   of  a  pixel   correlation  comparator  (such   as  Quam's);
recognition and location of an  expected object; or the location  and
extent of  an unknown  object.   It is  this latter application  that
will be described in my forthcoming thesis.